import java.util.ArrayList;
import java.util.List;

public class Solution173 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    List<TreeNode> list=new ArrayList<>();
    TreeNode current=null;

    public Solution173(TreeNode root) {
        TreeNode first=root;
        while (first.left!=null){
            list.add(first);
            first=first.left;
        }
        list.add(first);
        first.left=new TreeNode(-1);
        current=first.left;
        list.add(current);
    }

    public int next() {
        list.remove(list.size()-1);
        if (current.right!=null){
            TreeNode first=current.right;
            while (first.left!=null){
                list.add(first);
                first=first.left;
            }
            list.add(first);
            current=first;
        }else{
            current=list.get(list.size()-1);
        }
        return current.val;
    }

    public boolean hasNext() {
        return !(list.size()==1 && current.right==null);
    }

    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(7,new TreeNode(3),new TreeNode(15,new TreeNode(9),new TreeNode(20)));
        Solution173 solution173=new Solution173(treeNode);
        while (solution173.hasNext()){
            System.out.println(solution173.next());
        }
    }
}
